package com.shr.code_interview;

public class Solution_19 {
	public boolean match(char[] str, char[] pattern) {
		int strIdx = 0, patternIdx = 0;
		return matchCore(str, pattern, strIdx, patternIdx);
	}

	private boolean matchCore(char[] str, char[] pattern, int strIdx, int patternIdx) {
		if (strIdx == str.length && patternIdx == pattern.length)
			return true;
		if (strIdx != str.length && patternIdx == pattern.length)
			return false;
		if (patternIdx < pattern.length - 1 && pattern[patternIdx + 1] == '*') {
			if ((strIdx != str.length) && (str[strIdx] == pattern[patternIdx] || pattern[patternIdx] == '.'))
				return matchCore(str, pattern, strIdx + 1, patternIdx)
						|| matchCore(str, pattern, strIdx + 1, patternIdx + 2)
						|| matchCore(str, pattern, strIdx, patternIdx + 2);
			else
				return matchCore(str, pattern, strIdx, patternIdx + 2);
		} else if ((strIdx != str.length) && (str[strIdx] == pattern[patternIdx] || pattern[patternIdx] == '.'))
			return matchCore(str, pattern, strIdx + 1, patternIdx + 1);
		return false;
	}
}
